package HighMethod09;



class UFSets{
    private int[] parent;
    int size;
    public UFSets(int sz){
        size = sz;
        parent = new int[size];
        for(int i =0;i<size;i++){
            parent[i] = -1;
        }
    }

    /**
     * 寻找父节点
     * @param x
     * @return
     */
    public int FindParent(int x){
        while (parent[x]>=0){
            x = parent[x];
        }
        return x;
    }

    /**
     * 并操作
     * 1、加权规则
     *
     * @return
     */
    public boolean Union(int ia,int ib){
        boolean res = false;
        int pa = FindParent(ia);
        int pb = FindParent(ib);
        if(pa != pb){
            if(parent[pa] > parent[pb]){
                parent[pb] += parent[pa];
                parent[pa] = pb;
            }else {
                parent[pa] += parent[pb];
                parent[pb] = pa;
            }
            res = true;
        }
        return res;
    }

    /**
     * 打印聚类结果
     */
    public void PrintSet(){
        int s =0;
        for(int i =0;i<size;i++){
            if(parent[i] < 0){
                System.out.printf("s%d \n",s++);
                Print(i);
                System.out.println();
            }
        }
    }
    public void Print(int x){
        System.out.printf("%3d",x);
        for(int i=0;i<size;i++){
            if(i!=x&&parent[i]==x){
                Print(i);
            }
        }
    }
}

public class ClassSets {
    public static void main(String[] args) {
        UFSets ufSets = new UFSets(12);
        ufSets.Union(0,4);
        ufSets.Union(3,1);
        ufSets.Union(6,10);
        ufSets.Union(8,9);
        ufSets.Union(7,4);
        ufSets.Union(6,8);
        ufSets.Union(3,5);
        ufSets.Union(2,11);
        ufSets.Union(11,0);

        ufSets.PrintSet();      //打印聚类结果集合
    }
}
